package algorithm;

import java.util.ArrayList;

import structure.*;

public class utility {

	public utility(){
		
	}
	
	//restituisce tutti i nullable che ci sono nelle produzioni di una grammatica
	public static ArrayList<String> getNullable(ArrayList<production> productions){
		
		ArrayList<production> productionsCopy= new ArrayList<production>();
		productionsCopy= miscellaneous.cloneArray(productions);
		ArrayList<String> nullable= new ArrayList<String>();
		ArrayList<String> allLeftside= utility.getAllLeftSide(productionsCopy);
		boolean stop= false;
		
		while(!stop){
			
			ArrayList<Boolean> check= new ArrayList<Boolean>();
			
			for(production p : productionsCopy){
				
				ArrayList<String> rightside= p.getRightSide();
				ArrayList<String> rightsideNew= new ArrayList<String>();
				ArrayList<ArrayList<String>> matrixRightside= new ArrayList<ArrayList<String>>();
				ArrayList<Boolean> innerCheck= new ArrayList<Boolean>();
				boolean modified= false;
				
				for(String s : rightside){
					
					if(s.length() == 1 && allLeftside.contains(s)){
						
						//faccio l'unfold di s
						production tmpP= getProductionByLeftSide(s, productionsCopy);
						matrixRightside.add(singleUnfold(rightside, s, tmpP.getRightSide()));
						innerCheck.add(true);
					}
					else if(s.length() == 1 && s.equals("e")){
						ArrayList<String> tmpAR= new ArrayList<String>();
						tmpAR.add(s);
						matrixRightside.add(tmpAR);
						innerCheck.add(true);
					}
					else
						innerCheck.add(false);
				}
				
				for(boolean b : innerCheck){
					
					if(b==true){
						
						modified= true;
					}
				}
				//anche se è stata fatta una sola modifica devo aggiornare il rightside
				if(modified){
					
					for(ArrayList<String> ar : matrixRightside){
						
						for(String s : ar){
							
							if(!rightsideNew.contains(s)){
								
								rightsideNew.add(s);
							}
						}
					}
					//aggiorno il rightside
					p.setRightSide(rightsideNew);
					check.add(true);
				}
				else
					check.add(false);
			}
			
			for(boolean b : check){
				
				if(b==true){
					
					stop= true;
				}
			}
		}
		
		//dopo l'unfolding aggiungo i nullable all'array
		for(production p : productionsCopy){
			
			if(p.getRightSide().contains("e")){
				
				nullable.add(p.getLeftSide());
			}
		}
		
		return nullable;
	}
	
	//controlla che vi siano e-production
	public static boolean isThereEproduction(ArrayList<production> production){
		
		ArrayList<String> allRighside= new ArrayList<String>();
		
		for(production p : production){
			
			allRighside.addAll(p.getRightSide());
		}
		
		return allRighside.contains("e");
	}
	
	//crea le combinazioni dei caratteri di una stringa
	
	//restituisce tutte le stringhe che sono leftside
	public static ArrayList<String> getAllLeftSide(ArrayList<production> paramP){
		
		ArrayList<String> toReturn= new ArrayList<String>();
		for (production p :paramP){
			
			toReturn.add(p.getLeftSide());
		}
		
		return toReturn;
	}
	
	//restituisce la produzione in base al suo leftside
	public static production getProductionByLeftSide(String leftSide, ArrayList<production> paramP){
		
		for (production p : paramP){
			
			if(leftSide.equals(p.getLeftSide())){
				
				return p;
			}
		}
		
		return null;
	}
	
	//controlla se la produzione è trivial unit, e la elimina in caso affermativo
	public static void removeTrivialUnit(production p){
		/*
		 * una trivial unit è una produzione A->A
		 */
		ArrayList<String> rightside= p.getRightSide();
		ArrayList<String> rightsideNew= new ArrayList<String>();
		for(String s : rightside){
			
			if(!s.equals(p.getLeftSide())){
				
				rightsideNew.add(s);
			}
		}
		
		p.setRightSide(rightsideNew);
	}
	
	//restituisce la coda delle unit production
	public static void getUnitQueue(ArrayList<production> productions, FIFO fifo){
		/*
		 * una unit production è una produzione S->B
		 */
		for(production p : productions){
			
			String leftside= p.getLeftSide();
			ArrayList<String> rightside= p.getRightSide();
			
			for(String s : rightside){

				String tmpS= "";
				if(s.length() == 1 && Character.isUpperCase(s.toCharArray()[0])){

					tmpS= leftside + "->" +s;
					
					if(!fifo.contains(tmpS))
						fifo.push(tmpS);
				}
			}
		}
	}
	
	//rimpiazza un non terminale con le sue produzioni, se ce ne sono
	public static void replaceProduction(String left, String right, ArrayList<production> productions ){

		if(getAllLeftSide(productions).contains(left) && getAllLeftSide(productions).contains(right)){
			
			production leftProduction= utility.getProductionByLeftSide(left, productions);
			ArrayList<String> rightsideProductionLeft= leftProduction.getRightSide();
			ArrayList<String> rightsideProductionRight= utility.getProductionByLeftSide(right, productions).getRightSide();
			ArrayList<String> rightSideNew= new ArrayList<String>();
			
			for(int i=0; i<rightsideProductionLeft.size(); i++){
				
				if(right.equals(rightsideProductionLeft.get(i))){
					
					rightsideProductionLeft.remove(i);
					//opero la sostituzione delle produzioni
					for(int j=0; j<rightsideProductionRight.size(); j++){
						
						if(!rightsideProductionLeft.contains(rightsideProductionRight.get(j)) &&
								!rightSideNew.contains(rightsideProductionRight.get(j)))
							rightSideNew.add(rightsideProductionRight.get(j));
					}
					
					utility.removeTrivialUnit(leftProduction);
					break;
				}
			}
			leftProduction.addRightSide(rightSideNew);
		}
		else{
			//impossibile ma non si sa mai
			System.out.println("there aren't production to replace or to be replaced"); 
		}
	}
	
	//eseguo l'unfold delle produzioni unitarie es: S->A
	public static ArrayList<String> singleUnfold(ArrayList<String> rightside, String toBeUnfold, ArrayList<String> rightsideToUnfold){
		
		int position= miscellaneous.getPositionOfString(rightside, toBeUnfold);
		ArrayList<String> toReturn= new ArrayList<String>();
		toReturn.addAll(rightside);
		toReturn.remove(position);
		toReturn.addAll(rightsideToUnfold);
		return toReturn;
	}
	
	//controlla che una produzione sia in una forma adatta per la CNF
	public static boolean isForCNF(String rightside, ArrayList<String> VT){
		
		//caso S->a
		if(rightside.length() == 1) {

			if(VT.contains(rightside))
				return true;
			else if(miscellaneous.isANumber(rightside.charAt(0))){
				return true;
			}
		}
		//caso S->AA
		else if(rightside.length() == 2){
			
			char[] tmpC= rightside.toCharArray();
			char first= tmpC[0];
			char second= tmpC[1];
			if(Character.isUpperCase(first) && Character.isUpperCase(second)){
				return true;
			}
		}
		//caso S->A0B, AB0
		else if(rightside.length() == 3){
			
			char[] tmpC= rightside.toCharArray();
			char first= tmpC[0];
			char middle= tmpC[1];
			char last= tmpC[2];
			if(Character.isUpperCase(first)){
				//caso S->A0B
				if(miscellaneous.isANumber(middle) && !miscellaneous.isANumber(last) && Character.isUpperCase(last)){
					return true;
				}
				//caso S->AB0
				else if(!miscellaneous.isANumber(middle) && miscellaneous.isANumber(last) && Character.isUpperCase(middle)){
					return true;
				}
			}
		}
		//caso S->A1A2
		else if(rightside.length() == 4){

			char[] tmpC= rightside.toCharArray();
			char first= tmpC[0];
			char second= tmpC[1];
			char third= tmpC[2];
			char fourth= tmpC[3];
			
			if(Character.isUpperCase(first) && 
			   miscellaneous.isANumber(second) &&
			   Character.isUpperCase(third) &&
			   miscellaneous.isANumber(fourth)){
				
				return true;
			}
			
		}
			
		return false;
	}
	
	//controllo se una grammatica è in CNF
	public static boolean isCNF(ArrayList<production> productions, ArrayList<String> VT){
		
		for(production p : productions){
			
			for(String s : p.getRightSide()){
				
				if(isForCNF(s, VT) == false){
					
					return false;
				}
			}
		}
		
		return true;
	}
	
	//rimuovo dalle produzioni S->e se presente e ritorna true
	public static boolean removeSe(ArrayList<production> productions, String axiome){
		
		boolean toReturn= false;
		for(production p : productions){
			
			if(p.getLeftSide().equals(axiome)){
				
				if(p.getRightSide().contains("e")){
					
					p.removeProductionByString("e");
					toReturn= true;
				}
			}
		}
		
		return toReturn;
	}
	
	//riduce l'ordine di una produzione produzione
	public static ArrayList<production> reduceProductionOrder(String leftside, String rightside, NonTerminal nt, ArrayList<String> VT){
		
		ArrayList<production> toReturn= new ArrayList<production>();
		String firstPart= rightside.substring(0, 1);
		String secondPart= "";
		String remainingPart= "";
		boolean isAnumber= false;
		
		//se il primo carattere è un numero allora devo spostarlo nel leftside
		if(miscellaneous.isANumber(firstPart.charAt(0))){
			
			leftside+= firstPart;
			firstPart= rightside.substring(1, 2);
			if(rightside.length() > 3){
				secondPart= rightside.substring(2, 3);
				remainingPart= rightside.substring(3);
			}
		}
		//se il primo carattere non è un numero, e il rightside ha più caratteri
		else if(!miscellaneous.isANumber(firstPart.charAt(0)) && rightside.length() > 1){
			secondPart= rightside.substring(1, 2);
			if(miscellaneous.isANumber(secondPart.charAt(0))){

				remainingPart= rightside.substring(2);
				isAnumber= true;
			}
			else{
				remainingPart= rightside.substring(1);
			}
		}
		else{
			remainingPart= rightside.substring(1);
		}
		
		String tmpNT= nt.getNewTmpNT(), tmpProd= "";
		
		if(VT.contains(firstPart) ){
			
			//System.out.println("VT lo contiene firstpart= "+ firstPart + ", secondpart= " + secondPart + ", remainingpart= " + remainingPart);
			tmpProd= leftside + "->" + tmpNT + remainingPart + "|";
			toReturn.add(new production(tmpProd));
			tmpProd= tmpNT + "->" + firstPart + "|";
			toReturn.add(new production(tmpProd));
		}
		else{
			//System.out.println("VT non lo contiene firstpart= "+ firstPart + ", secondpart= " + secondPart + ", remainingpart= " + remainingPart);
			if(isAnumber){
				
				firstPart+= secondPart;
			}
			tmpProd= leftside + "->" + firstPart + tmpNT + "|";
			toReturn.add(new production(tmpProd));
			tmpProd= tmpNT + "->" + remainingPart + "|";
			toReturn.add(new production(tmpProd));
		}
		
		return toReturn;
	}
	
	//riduce l'ordine di una intera grammatica
	public static grammar reduceGrammarOrder(ArrayList<production> paramP, ArrayList<String> VN, ArrayList<String> VT){

		grammar toReturn= new grammar();
		toReturn.createItAll(paramP);
		
		if(!isCNF(paramP, VT)){

			toReturn.createItAll(paramP);
			ArrayList<production> productions= miscellaneous.cloneArray(toReturn.getAllProduction());
			ArrayList<production> tmpP= new ArrayList<production>();
			boolean stop= false;
			NonTerminal nt= new NonTerminal(VN);

			//System.out.println("toReturn prima della riduzione");
			
			while(!stop){
				
				for(production p : productions){
					
					ArrayList<String> tmpString= p.getRightSide();
					for(String s : tmpString){
						
						String tmpS= p.getLeftSide() + "->" + s + "|";
						//se la singola produzione non è in CNF e non esiste gia la riduco e poi l'aggiungo
						if(!isForCNF(s, toReturn.getVT()) && !miscellaneous.productionAlreadyExist(productions, tmpS)){

							tmpP.addAll(reduceProductionOrder(p.getLeftSide(), s, nt, toReturn.getVT()));
						}
						//altrimenti l'aggiungo direttamente
						else if(!miscellaneous.productionAlreadyExist(productions, tmpS)){
							
							tmpP.add(new production(tmpS));
						}
					}
				}
				//ho scorso tutte le produzioni e ho il mio nuovo array di produzioni 
				//controllo se è in CNF altrimenti ripeto il ciclo
				if(isCNF(tmpP, toReturn.getVT())){
					System.out.println("scorso tutte le produzioni, controllo se sono in CNF");
					stop= true;
					toReturn.createItAll(tmpP);
					
					return toReturn;
				}
				else{
					System.out.println("scorso tutte le produzioni, non sono in CNF");
				}
				
				productions.clear();
				productions= miscellaneous.cloneArray(tmpP);
				tmpP.clear();
			}
		}
		else{
			System.out.println("Grammar already in Chomsky Normal Form");
		}
		
		return toReturn;
	}
	
	//crea la recognition matrix
	public static matrix createRecognitionMatrix(ArrayList<production> productions, String w, matrix matrix, ArrayList<String> VT){
		
		//inizio la procedura per la creazione della recognition matrix
		
		//la dimensione della stringa di input
		int wLenght= w.length();
		//tutte le produzioni che producono un solo terminale
		ArrayList<production> singleProductions= getSingleProduction(productions, VT);
		//scorro le produzioni del tipo A->a
		//e aggiungo i leftside nella posizione corretta nella recognition matrix
		//la riga è fissata ad 1, la colonna varia
		for(int j=0; j<wLenght; j++){
			for(int i=0; i<singleProductions.size(); i++){
				
				String leftside= singleProductions.get(i).getLeftSide();
				String rightside= singleProductions.get(i).getRightSide().get(0);
				String ai= w.substring(j, j+1);
				
				if(rightside.equals(ai)){
					
					matrix.add(0, j, leftside);
				}
			}
		}
		
		//matrix.printIt();
		
		ArrayList<production> notSingleProduction= getNotSingleProduction(productions);
		//la prima riga è creata, creo la restante parte scorrendo le produzioni del tipo A->BC
		//e aggiungo i leftside nella posizione corretta nella recognition matrix
		//wLenght = numero di righe, la matrice è quadrata
		for(int i=1; i<wLenght; i++){
			for(int j=0; j<wLenght-i; j++){
				for(int k=0; k<i; k++){
					boolean added= false;
					for(production p : notSingleProduction){
						
						//p.printIt();
						String A= p.getLeftSide();
						for(String s : p.getRightSide()){
							//A->BC
							String firstpart= miscellaneous.splitItByNumbers(s)[0];//il primo non terminale
							String secondpart= miscellaneous.splitItByNumbers(s)[1];//il secondo non terminale
							//controllo che firstpart sia in posizione <k, j> e secondpart sia in posizione <i-k, j+k>
							int tmpI= i - 1 - k;
							int tmpJ= j + 1 + k;
							if(matrix.get(k, j) != null && matrix.get(tmpI, tmpJ) != null){
								if(matrix.get(k, j).contains(firstpart) && matrix.get(tmpI, tmpJ).contains(secondpart)){
									
									matrix.add(i, j, A);
									added= true;
									//System.out.println("Added " + A + " in position <" + i + "," + j + ">");
								}
							}
						}
					}
					
					if(!added && matrix.get(i, j) == null){
						matrix.add(i, j, " "); 
					}
				}
			}
		}
		//matrix.printIt();
		
		return matrix;
		
	}
	
	//restituisce tutte le produzioni che sono del tipo A->a
	//le produzioni passate devono essere in CNF
	public static ArrayList<production> getSingleProduction(ArrayList<production> productions, ArrayList<String> VT){
		
		ArrayList<production> toReturn= new ArrayList<production>();
		for(production p : productions){
			
			for(String s : p.getRightSide()){
				
				//if(Character.isLowerCase(s.charAt(0)) || VT.contains(s)){
				if(VT.contains(s)){	
					String tmpS= p.getLeftSide() + "->" + s + "|";
					production tmpP= new production(tmpS);
					toReturn.add(tmpP);
				}
			}
		}
		
		return toReturn;
	}
	
	//restituisce tutte le produzioni che sono del tipo A->BC
	//le produzioni passate devono essere in CNF
	public static ArrayList<production> getNotSingleProduction(ArrayList<production> productions){
		
		/*
		 * ci sono 4 possibilità
		 * A->BC, A->A0B, A->BA0, A->A0A1
		 */
		ArrayList<production> toReturn= new ArrayList<production>();
		
		for(production p : productions){
			
			ArrayList<String> tmpS= p.getRightSide();
			ArrayList<String> rightside= new ArrayList<String>();
			for(String s : tmpS){
				if(s.length() > 1){
					rightside.add(s);
				}
			}
			if(!rightside.isEmpty()){
				production newP= new production();
				newP.setLeftside(p.getLeftSide());
				newP.setRightSide(rightside);
				toReturn.add(newP);
			}
		}
		
		return toReturn;
	}
}
